package com.leetcode.partition3;

import com.leetcode.common.TreeNode;

/**
 * @author `RKC`
 * @date 2021/10/17 9:09
 */
public class LC230二叉搜索树中第K小的元素 {

    public static int kthSmallest(TreeNode root, int k) {
        for (int i = 1; i < k; i++) {
            root = delete(root);
        }
        TreeNode cur = root;
        while (cur.left != null) cur = cur.left;
        return cur.val;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5, new TreeNode(3, new TreeNode(1, null, new TreeNode(2)), new TreeNode(4)),
                new TreeNode(8, new TreeNode(6), new TreeNode(10)));
//        TreeNode root = new TreeNode(5, null, new TreeNode(8, new TreeNode(6), new TreeNode(10)));
        System.out.println(kthSmallest(root, 6));
    }

    private static TreeNode delete(TreeNode root) {
        TreeNode cur = root.left, parent = root;
        while (cur != null && cur.left != null) {
            parent = cur;
            cur = cur.left;
        }
        if (parent == root && parent.left == null) {
            //自己就是最小的值
            return root.right;
        }
        //删除parent下左边的cur节点
        parent.left = parent.left.right;
        return root;
    }
}
